class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        ListNode* guard1, * guard2, * tail1, * tail2;
        tail1 = guard1 = (ListNode*)malloc(sizeof(ListNode*));
        tail2 = guard2 = (ListNode*)malloc(sizeof(ListNode*));
        tail1->next = tail2->next = NULL;
        ListNode* cur = pHead;
        while (cur)
        {
            if (cur->val < x)
            {
                tail1->next = cur;
                cur = cur->next;
                tail1 = tail1->next;
            }
            else
            {
                tail2->next = cur;
                cur = cur->next;
                tail2 = tail2->next;
            }
        }
        tail1->next = guard2->next;
        tail2->next = NULL;

        return guard1->next;


    }
}; 
class PalindromeList {
public:

    struct ListNode* reverseList(struct ListNode* head) {
        struct ListNode* prev = NULL;
        struct ListNode* curr = head;

        while (curr) {
            struct ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }

        return prev;

    }

    struct ListNode* middleNode(struct ListNode* head) {
        struct ListNode* slow, * fast;
        slow = fast = head;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
        }

        return slow;
    }
    bool chkPalindrome(ListNode* A) {
        struct ListNode* mid = middleNode(A);
        struct ListNode* rhead = reverseList(mid);

        while (A && rhead)
        {
            if (A->val != rhead->val)
                return false;
            A = A->next;
            rhead = rhead->next;
        }
        return true;

    }
};

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    int len1, len2;
    len1 = len2 = 1;

    struct ListNode* tail1 = headA;
    struct ListNode* tail2 = headB;

    while (tail1)
    {
        tail1 = tail1->next;
        len1++;
    }
    while (tail2)
    {
        tail2 = tail2->next;
        len2++;
    }
    if (tail1 != tail2)
        return NULL;
    int gap = abs(len1 - len2);
    struct ListNode* longhead = headA;
    struct ListNode* shorthead = headB;
    if (len2 > len1)
    {
        longhead = headB;
        shorthead = headA;
    }
    while (gap--)
        longhead = longhead->next;
    while (shorthead != longhead)
    {
        shorthead = shorthead->next;
        longhead = longhead->next;

    }
    return longhead;



}